package com.le.basic.hash;

import java.util.HashMap;
import java.util.List;

/**
 * 并查集
 */
public class Code_02_UnionFind {
    public static class Node {
        Integer data;

        public Node(Integer data) {
            this.data = data;
        }
    }

    public static class UnionFindSet {
        public HashMap<Node, Node> fatherMap;
        public HashMap<Node, Integer> sizeMap;

        public UnionFindSet() {
            fatherMap = new HashMap<Node, Node>();
            sizeMap = new HashMap<Node, Integer>();
        }

        public void init(List<Node> nodes) {
            this.fatherMap.clear();
            this.sizeMap.clear();
            for (Node node : nodes) {
                this.fatherMap.put(node, node);
                this.sizeMap.put(node, 1);
            }
        }

        public Node findHead(Node node) {
            Node father = this.fatherMap.get(node);
            while (father != node){
                father = findHead(father);
            }
            this.fatherMap.put(node,father);
            return father;
        }

        public boolean isSampleSet(Node node1, Node node2){
            return findHead(node1) == findHead(node2);
        }

        public void union(Node node1, Node node2){
            if (node1 == null || node2 == null){
                return;
            }
            Node aHead = findHead(node1);
            Node bHead = findHead(node2);
            if (this.sizeMap.get(aHead) < this.sizeMap.get(bHead)){
                this.fatherMap.put(aHead,bHead);
                this.sizeMap.put(bHead,this.sizeMap.get(aHead) + this.sizeMap.get(bHead));
            }else {
                this.fatherMap.put(bHead,aHead);
                this.sizeMap.put(aHead, this.sizeMap.get(aHead) + this.sizeMap.get(bHead));
            }
        }

    }
}
